package leetcode.top100;


import baseclass.e_tree.Code01_ThreeTraverse;
import utils.TreeNode;

import java.util.Stack;

/**
 * 二叉树的三种遍历。递归略。
 * {@link Code01_ThreeTraverse}
 * @date 2020/4/7 15:51
 */
public class Code94_二叉树遍历 {
    public static void threeTraverse(TreeNode head, int type) {
        if (head == null) return;
        if (type == 0) System.out.print(head.val + " ");
        threeTraverse(head.left, type);
        if (type == 1) System.out.print(head.val + " ");
        threeTraverse(head.right, type);
        if (type == 2) System.out.print(head.val + " ");
    }

    /**
     * 先序遍历 ：  中->左->右
     */
    public static void preOrder(TreeNode tree) {
        if (tree == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(tree);
        while (!stack.isEmpty()) {
            tree = stack.pop();
            System.out.print(tree.val + " ");
            if (tree.right != null) {
                stack.push(tree.right);
            }
            if (tree.left != null) {
                stack.push(tree.left);
            }
        }
    }

    /**
     * 中序遍历 ：  左->中->右
     */
    public static void inOrder(TreeNode tree) {
        if (tree == null) return;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || tree != null) {
            //左侧链，如果有左孩子则一直入栈，滑下去
            if (tree != null) {
                stack.push(tree);
                tree = tree.left;
            } else {
                tree = stack.pop();
                System.out.print(tree.val + " ");
                //给右孩子，继续当前行为
                tree = tree.right;
            }
        }
    }

    /**
     * 后序遍历 ：  左->右->中
     * 很容易做到 中->右->左，先序遍历， 把遍历结果存储起来逆序输出。
     */
    public static void afterOrder(TreeNode tree) {
        if (tree == null) return;
        Stack<TreeNode> preStack = new Stack<>();
        preStack.push(tree);
        Stack<TreeNode> resStack = new Stack<>();
        while (!preStack.isEmpty()) {
            tree = preStack.pop();
            resStack.push(tree);
            //左孩子后遍历，先入栈
            if (tree.left != null){
                preStack.push(tree.left);
            }
            if(tree.right != null){
                preStack.push(tree.right);
            }
        }
        while (!resStack.isEmpty())
            System.out.print(resStack.pop().val+" ");
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(3);
        head.left.left = new TreeNode(4);
        head.left.right = new TreeNode(5);
        head.right.left = new TreeNode(6);
        head.right.right = new TreeNode(7);


        System.out.println("==========iter============");
        System.out.println("pre-order: ");
        threeTraverse(head, 0);
        System.out.println();
        System.out.println("in-order: ");
        threeTraverse(head, 1);
        System.out.println();
        System.out.println("pos-order: ");
        threeTraverse(head, 2);
        // recursive
        System.out.println();
        System.out.println("==============recursive==============");
        System.out.println("pre-order: ");
        preOrder(head);
        System.out.println();
        System.out.println("in-order: ");
        inOrder(head);
        System.out.println();
        System.out.println("pos-order: ");
        afterOrder(head);
        System.out.println();
    }
}
